package com.rui.study.algorithm.P_不同的二叉搜索树;

/**
 * @program: study
 * @description: n个节点组成的不同的二叉树个数，等于第1个节点作为根节点时组成树的个数，加上第2个
 * 节点作为根节点组成树的个数，以此类推直到第n个节点作为根节点组成树的个数，方程如下：G(n) = f(1)
 * + f(2) + ... + f(n)。当第i个节点作为根节点时，组成树的个数等于左子树的节点数乘以右子树的节点数
 * ，即f(i) = G(i-1) * G(n-i)，综上G(n) = G(0)*G(n-1) + G(1)*G(n-2) + ... + G(n-1)*G(0)，
 * 已知G(0) = 1，G(1) = 1
 * @author: Yaowr
 * @create: 2019-01-15 09:20
 **/
public class Solution {

    /**
     * ###思路###
     * 动态规划状态转移方程： G(n) = f(1) + f(2) + ... + f(n) 且 f(i) = G(i-1)*G(n-i)
     * 综上有：G(0) = 1 ，G(1) = 1 且 G(n) = G(0)*G(n-1) + G(1)*G(n-1) + ... + G(n-1)*G(0)
     * @param n
     * @return
     */
    public int numTrees(int n) {
        if (n == 0) {
            return 0;
        }
        int[] g = new int[n+1];
        g[0] = 1;
        g[1] = 1;
        for (int i = 2; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                g[i] += g[j] * g[i-j-1];
            }
        }
        return g[n];
    }


    public static void main(String[] args) {
        long begin = System.currentTimeMillis();
        Solution solution = new Solution();
        int result = solution.numTrees(3);
        long end = System.currentTimeMillis();
        System.out.println("不同的二叉搜索树：" + result + ", 耗时：[" + (end - begin) + "ms]");
    }

}
